package sortAlgorithm;

// 希尔排序
public class ShellSort {
    public static void shellSort(int[] arr){
        int gap; // 增量
        int len = arr.length;
        for (gap = len / 2; gap > 0; gap /= 2){
            for (int i = gap; i < len; i++) { // 这里其实就是插入排序
                int j = i;
                // 比较每组的值 如果后面的数小于前面的那个数 就进行交换
                while (j - gap >= 0 && arr[j] < arr[j-gap]){
                    int tmp = arr[j-gap];
                    arr[j-gap] = arr[j];
                    arr[j] = tmp;
                    j -= gap;
                }
            }
        }
    }

    //main
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,4,5,3,8,6};
        shellSort(nums);
        for (int i : nums) {
            System.out.println(i);
        }
    }
}
